\documentclass[]{article}   % list options between brackets
\usepackage{graphicx}
\usepackage{float}
\usepackage{epsfig}
\usepackage{subfigure}
\usepackage{moreverb}
\usepackage[margin=1in]{geometry}

% type user-defined commands here

\begin{document}

\title{Homework 3: On Nearest Neighbors and Decision Tree Classifiers \\CSE 592 Machine Learning}   % type title between braces
\author{Naresh P. Singh}         % type author(s) between braces
\maketitle

\renewcommand{\thesubfigure}{\thefigure.\arabic{subfigure}} 


\section{Problem 1. kNN(3)}
 \begin{figure}[H]
    \centering
    \mbox{
        \subfigure[]{\includegraphics[]{0.png}}\quad\subfigure[]{\includegraphics[]{0_686.png}}\quad\subfigure[]{\includegraphics[]{0_1434.png}}\quad\subfigure[]{\includegraphics[]{0_1622.png}}}\end{figure}
 \begin{figure}[H]
    \centering
    \mbox{
        \subfigure[]{\includegraphics[]{1.png}}\quad\subfigure[]{\includegraphics[]{1_1001.png}}\quad\subfigure[]{\includegraphics[]{1_1636.png}}\quad\subfigure[]{\includegraphics[]{1_64.png}}}\end{figure}
 \begin{figure}[H]
    \centering
    \mbox{
        \subfigure[]{\includegraphics[]{2.png}}\quad\subfigure[]{\includegraphics[]{2_1003.png}}\quad\subfigure[]{\includegraphics[]{2_724.png}}\quad\subfigure[]{\includegraphics[]{2_832.png}}}\end{figure}
 \begin{figure}[H]
    \centering
    \mbox{
        \subfigure[]{\includegraphics[]{3.png}}\quad\subfigure[]{\includegraphics[]{3_46.png}}\quad\subfigure[]{\includegraphics[]{3_19.png}}\quad\subfigure[]{\includegraphics[]{3_16.png}}}\end{figure}
 \begin{figure}[H]
    \centering
    \mbox{
        \subfigure[]{\includegraphics[]{4.png}}\quad\subfigure[]{\includegraphics[]{4_560.png}}\quad\subfigure[]{\includegraphics[]{4_65.png}}\quad\subfigure[]{\includegraphics[]{4_1930.png}}}\end{figure}
 \begin{figure}[H]
    \centering
    \mbox{
        \subfigure[]{\includegraphics[]{5.png}}\quad\subfigure[]{\includegraphics[]{5_92.png}}\quad\subfigure[]{\includegraphics[]{5_796.png}}\quad\subfigure[]{\includegraphics[]{5_528.png}}}\end{figure}
 \begin{figure}[H]
    \centering
    \mbox{
        \subfigure[]{\includegraphics[]{6.png}}\quad\subfigure[]{\includegraphics[]{6_1194.png}}\quad\subfigure[]{\includegraphics[]{6_1567.png}}\quad\subfigure[]{\includegraphics[]{6_460.png}}}\end{figure}
 \begin{figure}[H]
    \centering
    \mbox{
        \subfigure[]{\includegraphics[]{7.png}}\quad\subfigure[]{\includegraphics[]{7_1573.png}}\quad\subfigure[]{\includegraphics[]{7_1589.png}}\quad\subfigure[]{\includegraphics[]{7_980.png}}}\end{figure}
 \begin{figure}[H]
    \centering
    \mbox{
        \subfigure[]{\includegraphics[]{8.png}}\quad\subfigure[]{\includegraphics[]{8_38.png}}\quad\subfigure[]{\includegraphics[]{8_118.png}}\quad\subfigure[]{\includegraphics[]{8_229.png}}}\end{figure}
 \begin{figure}[H]
    \centering
    \mbox{
        \subfigure[]{\includegraphics[]{9.png}}\quad\subfigure[]{\includegraphics[]{9_825.png}}\quad\subfigure[]{\includegraphics[]{9_1231.png}}\quad\subfigure[]{\includegraphics[]{9_1387.png}}}\end{figure}
\section{Problem 2}
\subsection{Decision Tree for Information Gain}
\begin{verbatimtab}[8]
  VISIBILITY=yes
    ERROR=XL
      Output: noauto
    ERROR=LX
      Output: noauto
    ERROR=MM
      STABILITY=stab
        SIGN=pp
          MAGNITUDE=Low
            Output: auto
          MAGNITUDE=Medium
            Output: auto
          MAGNITUDE=Strong
            WIND=head
              Output: noauto
            WIND=tail
              Output: auto
          MAGNITUDE=OutOfRange
            Output: noauto
        SIGN=nn
          Output: noauto
      STABILITY=xstab
        Output: noauto
    ERROR=SS
      STABILITY=stab
        MAGNITUDE=Low
          Output: auto
        MAGNITUDE=Medium
          Output: auto
        MAGNITUDE=Strong
          Output: auto
        MAGNITUDE=OutOfRange
          Output: noauto
      STABILITY=xstab
        Output: noauto
  VISIBILITY=no
    Output: auto
\end{verbatimtab}
\subsection{Decision Tree for Information Gain Ratio}
\begin{verbatimtab}[8]
  VISIBILITY=yes
    STABILITY=stab
      ERROR=XL
        Output: noauto
      ERROR=LX
        Output: noauto
      ERROR=MM
        SIGN=pp
          MAGNITUDE=Low
            Output: auto
          MAGNITUDE=Medium
            Output: auto
          MAGNITUDE=Strong
            WIND=head
              Output: noauto
            WIND=tail
              Output: auto
          MAGNITUDE=OutOfRange
            Output: noauto
        SIGN=nn
          Output: noauto
      ERROR=SS
        MAGNITUDE=Low
          Output: auto
        MAGNITUDE=Medium
          Output: auto
        MAGNITUDE=Strong
          Output: auto
        MAGNITUDE=OutOfRange
          Output: noauto
    STABILITY=xstab
      Output: noauto
  VISIBILITY=no
    Output: auto
\end{verbatimtab}
For the first tree, the split is chosen based on the informtion gain from the split. All the attributes are considered equally irrespective of multiple values they can take. For the second tree, the split is considered based on gain ratio. With gain ratio, we favor attributes with lesser values over those with large number of values. This usually gives a simpler tree. Also, the attributes with large number of values might not even have sufficient samples for learning. This would cause overfitting or give us a less general model. In our experiments, we notice that with gain ratio, STABILITY attribute is promoted over ERROR. This is because STABILITY is a two valued attribute as opposed to ERROR which can take four values. Thus, the second tree is more general than the first.

\end{document}